package com.redis.hyperloglog;

import java.util.concurrent.ThreadLocalRandom;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *
 * @author lzy
 * @date 2020-10-01 下午4:34
 */
public class PfAlgorithmTest2 {
    public static void main(String[] args) {
        for (int i = 100000; i < 1000000; i += 10000) {
            Experiment exp = new Experiment(i);
            exp.work();
            double est = exp.estimate();
            System.out.printf("%d %.2f %.2f\n", i, est, Math.abs(est - i) / i);
        }
    }

    static class BitKeeper {
        private int maxbits;

        private static int lowZeros(long value) {
            int i = 1;
            for (; i < 32; i++) {
                if (value >> i << i != value) {
                    break;
                }
            }
            return i - 1;
        }

        public void random(long value) {
            int bits = lowZeros(value);
            if (bits > maxbits) {
                maxbits = bits;
            }
        }
    }

    static class Experiment {
        private final int n;
        // 构造k个BitKeeper进行加权平均
        private final int k;
        private final BitKeeper[] bitKeepers;

        public Experiment(int n) {
            this(n, 1024);
        }

        public Experiment(int n, int k) {
            this.n = n;
            this.k = k;
            this.bitKeepers = new BitKeeper[k];

            for (int i = 0; i < k; i++) {
                this.bitKeepers[i] = new BitKeeper();
            }

        }

        public void work() {
            for (int i = 0; i < this.n; i++) {
                long m = ThreadLocalRandom.current().nextLong(1L << 32);
                BitKeeper keeper = bitKeepers[(int) (((m & 0xfff0000) >> 16) % bitKeepers.length)];
                keeper.random(m);
            }
        }

        public double estimate() {
            double sumbitsInverse = 0.0;
            for (BitKeeper bitKeeper : bitKeepers) {
                sumbitsInverse += 1.0 / (float) bitKeeper.maxbits;
            }
            double avgBits = (float) bitKeepers.length / sumbitsInverse;
            return Math.pow(2, avgBits) * this.k;
        }
    }
}
